COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\rm
C00008 ENDMK
C⊗;
\rm
\magnification=\magstephalf
\nopagenumbers

\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}

\line{\sevenrm A02.tex[154,rwf] \today\hfill}

\vskip 7pt

\centerline{Solutions to CS154 final exam, spring 1984.}

\vskip 7pt

\noindent
1. Yes. If a set $L$ is RE, there is a TM which accepts it. If $G$ is
an arbitrary gsm mapping, then $G↑{-1}$ is also a gsm mapping, and
$G(L)$ is accepted by the TM obtained by composing a gsm for $G↑{-1}$
with the TM for $L$. This machine accepts $x$ iff $∃y$ such that $xG↑{-1}y$ 
(i.e. $yGx$) and $yεL$.

\vskip .7pt

\noindent
4. Convert the gsm to the form where inputs and outputs are at most one
character. Construct a NPDA whose states and connections are the same as
those of the gsm, except:

\vskip 7pt

(1) If $\quad i$ \hskip .25in $↑{(/x}$ \hskip .25in $j\quad$ in the gsm, then

\vskip .125in

$\quad i$ \hskip .5in Push 1 \hskip .5in Read \hskip .25in $↑x$ 
\hskip .25in $j\quad$ in the NPDA

\vskip .125in

\hskip 1.75in $↑{\rm other}$\hskip .25in Reject

\vskip .125in

(2) If $\quad i$ \hskip .25in $↑{)/x}$ \hskip .25in $j\quad$ in the gsm, then

\vskip .125in

$\quad i$ \hskip .5in Empty?\hskip .5in No\hskip .5in Pop\hskip .25in $↑1$
\hskip .5in Read\hskip .25in $↑x$\hskip .25in $j\quad$ in the NPDA

\vskip .125in

\hskip 1in Yes\hskip .25in Reject \hskip 1.75in $↑{\rm other}$\hskip .25in Reject

\vskip .125in

(3) If $\quad i$ \hskip .25in $↑{\epsilon /x}$\hskip .25in $j\quad$ in the gsm, then

\vskip .125in

$\quad i$\hskip .5in Read \hskip .25in $↑x$\hskip .5in $j\quad$ in the NPDA

\vskip .125in

\hskip .75in $↑{\rm other}$\hskip .5in Reject

\vskip 7pt

where the reads are omitted if $x=\epsilon$. (The NPDA accepts only if the 
stack is empty.) The NPDA accepts exactly the gsm's transductions of the
one-parenthesis language, and since only one symbol goes on the stack, it is a
one-counter machine.


\vskip 7pt

\noindent
5. Assume the 2CM $M$ has counters $X$ and $Y$. Construct a composition of
$M↓x$ with $M↓y$. $M↓x$ simulates $M$, except that

(1) It does not have counter $Y$; it guesses, nondeterministically, the outcome
of operations on counter $Y$.

(2) It outputs a complete running description of its computation. $M↓y$ reads
the output of $M↓x$, and performs the operations on counter $Y$, checking that
$M↓x$ guessed right about the behavior of $Y$. $M↓y$ outputs just the
symbols of its input that are output symbols of $M$.

\vskip 7pt

\noindent
7. No. If $L$ were a CFL, intersecting with $A↑*C↑*B↑*D↑*$ would give 
$A↑nC↑nB↑nD↑n$ as a CFL. A gsm transduction that maps $A$ into $A$,
$C$ into $B$, $B$ into $C$, $D$ into $\epsilon$, 
would give $A↑nB↑nC↑n$ as a CFL; it is a notorious non-CFL.

\vskip 7pt

\noindent
8. A non-computation is a string which (locally) violates the state transition
rules, or in which the operations of a device are not consistent with its
definition. Then the set of non-computations is the union of a regular set
and a language of strings showing incorrect behavior for each device.
For the Turing machine, behavior is incorrect if the machine writes or reads
a symbol on the tape, and later finds a different symbol there. A N1CM
can check this, by non-deterministically deciding which read or write to
check, setting its counter to zero, using the counter to record how far from
the checked square it is, and checking when the counter is zero. The language
of non-computations is then the union of a N1CM language and a regular language;
i.e., it is a N1CM language.

\vfil\end